鏈結串列可以讓你更加認識指標的使用。

我認為這是精進自己指標能力的開始，包括「取值」、「取址」、「動態配置記憶體」。

鏈結串列

鏈結串列又可以簡單分成「單向鏈結串列」與「雙向鏈結串列」。

原理概述

鏈結串列是由許多節點構成的一種資料結構，節點中紀錄資料內容之外，也記錄其鄰居節點。
紀錄鄰居節點的變數我們稱為鏈結，因此我們稱「節點」為「資料」+「鏈結」，而這些節點相連成「鏈結串列」。

鏈結串列最重要的部分是紀錄「頭部節點 head」的變數，因為每一個節點都包含著至少一個鏈結，我們可以從「鏈結」知道下一個節點。如果指向的節點，其鏈結指向 NULL，代表這個節點是鏈結串列的最後一個。

從外型來看

• 單向鏈結串列
  

• 雙向鏈結串列
  

鏈結串列的缺點（無法隨機存取）

陣列具有隨機存取的功能，即 arr[idx] 來取得某一個列表元素，且所費時間僅 O(1)。

鏈結串列則沒有隨機存取的功能，當我們要取得第 idx 個元素時，我們需要從頭開始搜尋，直到找到該元素。

鏈結串列的優點（插入、刪除）

當我們使用陣列時，我們要實行插入與刪除，我們需要搬動大量的元素（取決於列表大小）。

如果我們使用鏈結串列，我們可以用 O(1)的時間完成插入與刪除，我們只需要把該節點的前一項的鄰居設為該節點的下一項。

如上圖：
假設我們要刪除資料內容為 5 的節點
綠色箭頭代表改變的鏈結

如上圖：
假設我們要新增資料內容為 5 的節點
綠色箭頭代表改變的鏈結

也許聽完上述的說明，仍不清楚鏈結串列！沒關係，接下來我們會更清楚的介紹鏈結串列。

下一篇開始，我們會開始實作鏈結串列！